/*
 * @Author: Vorga
 * @LastEditors: Vorga
 */
#include "heap_tree.h"

Heap* create_ht(size_t size)
{
    //    TreeArray* heap = create_ta(arr);
    //    for(int i = heap->cnt/2; i > 0; i--){
    //        _createHeap(heap->arr,i,heap->cnt);
    //    }
    //    return heap;
    Heap* heap = malloc(sizeof(Heap));
    heap->arr = malloc(sizeof(void*) * size);
    heap->size = size;
    heap->cnt = 0;
    return heap;
}

static void _adjust_ht(Heap* heap, int root)
{
    //    for(int i = cnt; i > 1; i--)
    //    {
    //        if(arr[i/2-1] < arr[i-1]){
    //            swap(arr[i/2-1],arr[i-1]);
    //            i = cnt;
    //        }
    //    }
    while (root * 2 <= heap->cnt) {
        int min = root * 2;
        if (min < heap->cnt && 1 == heap->cmp(heap->arr[min - 1], heap->arr[min])) {
            min++;
        }
        if (1 != heap->cmp(heap->arr[root - 1], heap->arr[min - 1])) {
            return;
        }
        swap(heap->arr[root - 1], heap->arr[min - 1]);
        root = min;
    }
    //if(0 == len/2) return;
    //if(arr[len/2-1] < arr[len-1]) swap(arr[len/2-1],arr[len-1]);
    //_createHeap(arr,len/2);
    //_createHeap(arr,len-1);
}

bool empty_ht(Heap* heap)
{
    return 0 == heap->cnt;
}

bool full_ht(Heap* heap)
{
    return heap->size == heap->cnt;
}

void traversal_ht(Heap* heap, FUNC show)
{
    for (int i = 0; i < heap->cnt; i++) {
        show(heap->arr[i]);
    }
}

void* top_ht(Heap* heap)
{
    return heap->arr[0];
}

bool pop_ht(Heap* heap)
{
    if (empty_ht(heap) || NULL == heap->cmp) return false;
    heap->arr[0] = heap->arr[--heap->cnt];
    _adjust_ht(heap, 1);
    return true;
}

bool push_ht(Heap* heap, void* data)
{
    if (full_ht(heap) || NULL == heap->cmp) return false;
    heap->arr[heap->cnt++] = data;
    for (int i = heap->cnt / 2; i > 0; i--) {
        _adjust_ht(heap, i);
    }
    return true;
}
//堆排序
bool sort_ht(Heap* heap)
{
    if (NULL == heap->cmp) return false;
    for (int i = heap->cnt - 1; i > 0; i--) {
        swap(heap->arr[i], heap->arr[0]);
        _adjust_ht(heap, i);
    }
    return true;
}

void destory_ht(Heap* heap)
{
    if (NULL == heap->cmp) return;
    while (!empty_ht(heap))pop_ht(heap);
}

void set_cmp_ht(Heap* heap, CMP cmp)
{
    heap->cmp = cmp;
}
